A lock is a synchronization mechanism that is often used for enforcing mutual exclusion in a system with multiple threads contending for a resource. Software threads are typically elements of a process and are typically used in multi-core systems. Software threads typically are coordinated so that only one thread has access to a critical resource like a shared data, a critical section, etc. at any given instant in time. Locks typically ensure that only the thread owning the lock is allowed access to the critical section while the other threads have to retry later to gain access. Locks are typically implemented as a variable in a memory location. In one embodiment, when the lock variable is set to logic 0, the lock is free, and when a thread acquires the lock, the thread has to first check the lock variable to ensure it is free. If free, the thread acquires the lock by storing a logic 1 to the variable. Any other threads attempting to acquire the lock during this time will read a value of logic 1 in the lock variable and will have to retry lock acquisition. When the thread owning the lock is ready to release the lock, the thread stores the value of logic 0 into the variable. Other threads waiting to acquire the lock will compete for the lock and the winning thread will acquire the lock. The remaining threads will retry.
Two common strategies when a thread tries to acquire a lock and finds that the lock is owned by another thread are yielding and spinning. Yielding allows the thread owning the lock to continue to use the resource pertaining to the lock while the thread wanting the lock waits a period of time before attempting again to acquire the lock. A consequence of this strategy is that the lock may be released before the thread desiring to acquire the lock re-attempts to acquire the lock, thus delaying execution of the thread desiring the resource associated with the lock. Spinning is a strategy where the thread desiring the lock keeps trying to acquire the lock again and again until the thread acquires the lock. The consequence of spinning is increased bus traffic.
When a number of threads try to acquire a lock at the same time, the lock is said to be “contended.” Contended locks generate a lot of traffic on the memory buses due to the nature of lock acquire/lock release and cache coherence protocols. Knowing if a lock is contended can be useful. If a thread knows that a lock is contended, the thread can yield without checking the lock variable, which can reduce bus traffic. Knowing if a lock is contended also has the benefit of reducing energy usage if the system is not loaded with threads or increasing throughput if threads from another process can be scheduled. If the lock is not contended, the thread can spin and immediately access the lock and benefit from lower lock acquire latency.
One common cache coherence strategy is the MESI coherence protocol, where MESI stands for Modified, Exclusive, Shared, and Invalid. The MESI coherence protocol is widely used and leads to scenarios with a lot of bus traffic for contended locks, especially with spinning.